% !Mode:: "TeX:UTF-8" 

\BiChapter{绪论}{Introduction}

\BiSection{课题来源及研究意义}{Background, objective and significance of the research}

\BiSubsection{课题来源}{Sources of the Research}
本课题来源于国防科技创新特区H863计划重点项目。


\BiSubsection{课题研究背景与意义}{Background and significance of the thesis}

%多智能体简介
多智能体系统(Multi-Agent System,MAS)是指多个具备一定感知、计算和通信能力的智能体通过交互、协作行为组织在一起的复杂网络系统，具备复杂系统的三种基本特性，即学习性，适应性和涌现性\citeup{Huang2011ComplexSys,金士尧2010复杂系统涌现与基于整体论的多智能体分析}。多智能体系统的本质是一组人造的群体社会，是对生物界群居群聚行为的模拟，主旨在于为群体中的每一个个体都分配较低复杂度的子任务，允许群体之间通过交互协作等手段寻找复杂问题的解。多智能体系统的涌现性具体表现为，系统中每个个体通过通信、观测等手段与其他个体互通有无，相互协作，从而通过发挥群体的规模优势，弥补个体的生存和功能劣势，实现群体利益最大化。群体中每个个体之间的关系并不是简单的功能叠加，而是通过合理的组织结构和群体体系实现资源的优势配给与有效分工，从而实现$1+1>2$的增益效果。相较于单个智能体系统，多智能体系统具备更高的容错性、鲁棒性，以及较低的成本。近年来，随着嵌入式计算和通信等技术的成熟，多智能体系统的概念也逐渐从最初特指的计算节点网络，拓展为当前由具备更高自主能力、交互能力移动机械平台网络，如多机器人系统、无人机集群系统、卫星编队等，成为机器人、计算机、控制等多个领域重要的研究方向。

构型的设计、变换和保持是多智能体系统实现功能涌现性的关键和基础。
生物集群通过形成、保持和变换构型来进行群体性协作，以发挥个体不具备的优势和功能，从而完成个体无法实现的任务。例如，当面对危险时，鱼群、羊群通过聚集性逡游和奔跑来实现对捕猎者的防御，群体外围通常由健壮个体组成，将集群的幼体维护在队形中央，从而实现群体生存和繁衍利益的最大化。狼群、鲨群等捕食者群体内部通常存在严格的社会体系和职能分工，在首领的“指挥协调”下，集群中的个体各司其职，通过密切的构型协同变换，实现对猎物的包围、分割、诱捕等战术，从而提升捕猎效率。以雁群为代表的鸟类群体在长途迁徙过程中会变换不同的队形，如“人”字形和“一”字形，以节约飞行能量。因此，构型的设计、控制和变换是生物集群系统实现群体效益最大化的重要手段和方法。从系统论的观点出发，底层个体之间、个体与环境之间的非线性相互作用决定了复杂系统的涌现性层次，导致复杂系统的行为状态在确定和混沌之间、有序和无序之间转换。因此。只有将多智能体系统内的节点按照合理的“构型”组织在一起，内部节点之间、节点与环境之间才能发挥积极的、正向的交互、激励与反馈，从而促使多智能体系统更多未知能力的涌现。因此，构型协同控制和规划是多智能体系统的基础研究内容。

%拒止环境内涵
上世纪八十年代以来，多智能体系统在理想环境下的研究取得了巨大成果，搭建了近乎完善理论框架。以此为背景，越来越多的研究开始关注多智能体在更为复杂环境中的应用。本文将主要研究一类导航、通信过程受限拒止的环境。在理想环境中，多智能体系统内部的节点通常假定自身状态精确已知，且可以获得及时、完整的通信交互数据，从而可以重点研究系统的协作机制和分布式特性。然而在许多实际应用中，一方面，在对抗环境下，状态估计所依赖的外部信息源(如GNSS定位卫星、锚节点、路标点)等存在被摧毁、屏蔽或欺骗的风险；通信过程也容易被干扰、压制。另一方面，即使在非对抗环境下，系统的状态信息通常是通过融合对环境的观测数据得到的，因此会存在估计不确定性，系统的某些状态甚至是不可观测的；通信过程更是存在视线遮挡、功率、带宽等因素的限制，会产生时变通信拓扑、时延、丢包等通信问题。因此受限拒止环境将存在高度的\textbf{不确定性}、\textbf{不可预测性}以及\textbf{不可靠性}。

在严苛的外部环境下，多智能体系统必须实现更高层次的功能涌现，才能保证任务的顺利执行。因此，受限拒止环境对多智能体系统的涌现性提出了更高的要求，必须对受限拒止环境下构型的协同控制和规划方法进行深入研究。

本学位论文研究的构型控制和规划问题与当前研究中的(队形)编队控制、路径规划等内容既密切相关又有所区别。编队控制是指通过设计合适的控制律使得多智能体所有的节点状态达到预设约束；路径规划是寻找一系列包含<节点状态、控制输入>的序列，使得多智能体节点的状态可以自主地、安全地在自由运动空间中到达给定的目标状态。因此编队控制和轨迹规划的研究内容主要是关注节点在\textbf{空间拓扑}上的实时相对位姿关系。然而本文的构型控制和规划的根本目的是为了服务于多智能体系统的性能涌现，需要更加关注以通信、感应、观测等行为为代表的系统底层的相互作用。因此本文研究的\textbf{构型控制和规划问题，其本质是交感拓扑下的编队控制和轨迹规划问题。}

%拒止环境对构型控制和规划方法的影响
受限拒止环境在交感拓扑上对多智能体系统构型协同控制和规划过程产生的影响主要可以表现为如下三类：
\begin{enumerate}
	\item[(1)] GNSS信号拒止，即多智能体系统内的节点无法获得其在绝对坐标系下精确的状态观测;
	\item[(2)] 环境具有高不确定性，即节点的观测过程和运动过程都存在未知扰动或者未建模的误差;
	\item[(3)] 相对观测通信过程受限，即受限于设备元器件的物理极限，通信和观测模型是有界的。
\end{enumerate}

基于上述分析，本学位论文对拒止环境下多智能体系统构型协同控制与规划方法进行进一步深入研究。首先，对一类包围构型协同控制问题，研究基于局部坐标系下相对观测数据的一致性协同控制方法；其次，针对构型控制与协同定位之间存在耦合的问题，研面向PDOP定位构型的构型控制方法，探讨通过构型控制改善协同定位性能的方法；然后，针对构型规划中的状态不确定性问题，研究基于信念空间的构型协同规划方法；最后，针对信念空间规划方法中节点测量传感器感应能力受限的问题，进一步研究基于概率交感拓扑的构型规划方法，提升了构型规划效率。期望本文的研究成果能够为多智能体系统在复杂拒止场景中的大规模应用提供技术储备和理论支撑。



%总体而言，对抗和非对抗的拒止环境对多智能体系统任务执行的影响，大体可以总结为如下四类约束：
%
%1. 任务约束：在保证任务目标完成的前提下，确保任务执行过程中的时间、过载、燃料等指标满足特定约束条件;
%
%2. 硬件约束：机械平台受物理规律影响而存在的约束条件，如计算资源、存储资源限制，各类传感器、执行机构的实际物理限制，如通信设备存在的延时、执行机构因机械惯性而存在较大的响应时间常数等;
%
%3. 环境约束：指外部环境因自然变化过程或者对抗行为而存在高不确定性。而导致的机器人在与环境的交互行为中存在不可靠、不稳定的情况。例如对抗环境中存在的GNSS信号诱导、欺骗、拒止；通信过程受到的屏蔽、干扰；沙漠、海洋等环境中定位信息稀缺、匮乏等条件;
%
%4. 安全性约束：指系统平台在完成任务目标以外为了维持生存所施加的自我约束，如额外的防碰撞能力、抗打击性、可拓展性等需求。

% 引入复杂场景
%\BiSubsection{构型控制与规划问题}{Configuration Control and Planning Problem} \label{subsec. problems}
%
%生物集群通过形成、保持和变换构型来进行群体性协作，以发挥个体不具备的优势和功能，从而完成个体无法实现的任务。例如，当面对危险时，鱼群、羊群通过聚集性逡游和奔跑来实现对捕猎者的防御，群体外围通常由健壮个体组成，将集群的幼体维护在队形中央，从而实现群体生存和繁衍利益的最大化。狼群、鲨群等捕食者群体内部通常存在严格的社会体系和职能分工，在首领的“指挥协调”下，集群中的个体各司其职，通过密切的构型协同变换，实现对猎物的包围、分割、诱捕等战术，从而提升捕猎效率。以雁群为代表的鸟类群体在长途迁徙过程中会变换不同的队形，如“人”字形和“一”字形，以节约飞行能量。因此，构型的设计、控制和变换是生物集群系统实现群体效益最大化的重要手段和方法。
%
%从系统论的观点出发，底层个体之间、个体与环境之间的非线性相互作用决定了复杂系统的涌现性层次，导致复杂系统的行为状态在确定和混沌之间、有序和无序之间转换。因此系统的实时构型是决定多智能体系统涌现性的关键因素之一。只有将多智能体系统内的节点按照合理的“构型”组织在一起，节点之间、节点与环境之间才能发挥积极的、正向的交互、激励与反馈，从而促使多智能体系统更多未知能力的涌现。因此，构型协同控制和规划是多智能体系统的基础研究内容。
%
%本章研究的构型控制和规划问题与当前研究中的(队形)编队控制、路径规划等内容既密切相关又有所区别。编队控制是指通过设计合适的控制律使得多智能体所有的节点状态达到预设约束；路径规划是寻找一系列包含\{ 节点状态、控制输入 \}的序列，使得多智能体节点的状态可以自主地、安全地在自由运动空间中到达给定的目标状态。因此编队控制和轨迹规划的研究内容主要是关注节点在\textbf{空间拓扑}上的实时相对位姿关系。然而本文的构型控制和规划的根本目的是为了服务于多智能体系统的性能涌现，需要更加关注以通信、感应、观测等行为为代表的系统底层的相互作用。因此本文研究的\textbf{构型控制和规划问题，其本质是交感拓扑下的编队控制和轨迹规划问题。}
%
%%拒止环境对构型控制和规划方法的影响
%
%
%复杂拒止环境在交感拓扑上对多智能体系统构型协同控制和规划所施加的影响主要可以归纳为如下三类：
%\begin{enumerate}
%	\item[(1)] 无法获得系统节点在绝对坐标系下精确的状态观测;
%	\item[(2)] 相对观测通信过程受限;
%	\item[(3)] 环境具有高不确定性。
%\end{enumerate}


%基于上述问题，本课题对拒止环境下多智能体系统构型协同控制与规划方法进行进一步深入研究。首先，对一类包围构型协同控制问题，研究基于相对观测数据的一致性协同控制方法；其次，针对构型与定位存在耦合的问题，研究基于PDOP定位构型的构型控制方法，通过改变多智能体构型来主动地改善定位精度；然后，针对构型规划中的状态不确定性问题，研究基于信念连续空间的构型协同规划方法，使用数值梯度下降方法生成候选轨迹，从而减轻了“维度灾难”问题；最后，针对信念状态空间中节点测量传感器感应能力受限的问题，进一步研究基于概率交感拓扑的构型规划方法，提升了构型规划效率。期望本文的研究成果能够为多智能体系统在复杂拒止场景中的大规模应用提供技术储备和理论支撑。

\BiSection{国内外研究现状}{Current status for related researches}

本学位论文的研究内容涉及多个研究热点。第一，本文的研究对象多智能体系统目前已经有30多年的研究历史，是许多领域的重要研究分支，取得了众多突破性进展。第二，由于构型与编队(队形)两个概念之间的深刻联系，构型的协同控制与规划问题与传统的“编队控制”以及“路径规划”之间也存在密切联结。第三，由于拒止环境的限制，依靠相对测量的协同定位技术成为多智能体系统进行状态估计的可靠方法，而协同定位又与构型控制之间存在耦合关系。最后，由于实际应用中智能体的运动过程和观测过程都存在噪声干扰，任何协同定位技术得到的状态估计都必定存在不确定性，而不确定的状态观测将增加构型规划问题的复杂度。

因此本节首先将典型拒止环境下多智能体系统在多个领域的应用发展进行综述。然后将与本学位论文相关的国内外研究的现状总结归纳为如下四个主题，分别为：第一，构型控制方法，首先梳理传统空间拓扑下编队控制的重要研究进展，然后针对交感拓扑下的构型控制方法进行综述；第二，多智能体系统轨迹规划方法，首先归纳针对单体的轨迹规划方法研究进展，然后将这些方法在多智能体系统下的应用进行综述；第三，协同定位方法，首先分析GNSS信号弱点，然后介绍协同定位方法的发展现状，并根据已有研究结果重点分析了协同定位与构型之间的耦合关系；第四，不确定性规划方法，首先介绍了通用部分可观测马尔可夫决策过程(Partially Observable Markov Decision Process, POMDP)的研究现状，然后分析了该问题在多智能体系统上的应用。本节最后结合受限拒止环境的特性，总结归纳多智能体系统构型协同控制和规划方法面临的问题和挑战。


\BiSubsection{典型拒止环境中多智能体系统的应用}{Survey of multi-agent system in denied environments}
本学位论文涉及的拒止特性主要来源于多智能体系统在导航、通信过程受到的各类限制和约束。这些限制和约束广泛存在于军事对抗、外太空探索、深海探测等典型任务中。

首先，在军事应用上，美军早在二十一世纪初就已经开始发展“集群智能”作战概念，其中具备强机动性、攻击性的无人机集群成为其重点发展对象。在2005年发布的《无人机系统路线图2005-2030》中，全自主的无人机集群技术成为了美国国防部的终极发展目标。在随后发布的《空军未来作战概念(2015)》《2016-2036年小型无人机系统飞行规划》以及《2018年国防部人工智能战略摘要》中都重点突出了无人机集群技术的重要性。以此为契机，美国高级研究计划局(DARPA)率先开展了一系列基于无人机集群的作战概念研究。

2015年，DARPA发布“拒止环境协同作战”（CODE）项目，旨在搭建具备先进协同算法和监控技术的模块化软件体系，保障无人机集群系统在通信限制和GPS定位信息拒止的环境下具备高自主功能，可以自发完成目标搜寻、识别、跟踪和打击一体化，提高无人机集群在复杂环境下的生存能力和协同作战能力，同时减少人在回路中的参与，降低对操作人员的要求。目前CODE项目已经在2019年完成三期验证工作。6架RQ-23虎鲨无人机以及14个虚拟无人机组成的集群，搭载由雷神公司以及约翰斯-霍普金斯大学合作研发的自主协同算法软件，在美国亚利桑那州尤马县的沙漠中完成了在通信拒止和GPS信号拒止环境下的复杂协同任务。

\begin{figure}[htbp]
	\centering	
	
	\subfigure{\label{subfig. discretizationArea}}\addtocounter{subfigure}{-2}
	\subfigure[Indication for the CODE program]{\subfigure[Code项目整体示意图]{\includegraphics[width = 0.45\textwidth]{figures/DARPA_CODE_concept.jpg}}}	
	\null\hfill
	\subfigure{\label{subfig. discretizationBoundary}}\addtocounter{subfigure}{-2}
	\subfigure[The TigerShark UAV for third phase]{\subfigure[待执行第三阶段试飞任务的虎鲨无人机]{\includegraphics[width = 0.45\textwidth]{figures/CODE_TigerShark.jpg}}}
	
	\bicaption[fig. PDOPdiscretizationAreaBoundary]{}{CODE项目( 图片来源：DARPA )}{Fig.$\!$}{An overview of the CODE program, source DARPA}
	\vspace{-0em}
\end{figure}

DARPA在2017年启动的“进攻性集群使能战术”(OFFSET)项目,旨在提升不同军种和不同装备之间的协同自主作战能力。OFFSET项目计划利用大规模空中和地面自主机器人在城市地区实行空中侦察和定点清剿任务，从而为其他军种的战术实施提供便利，大幅提高城市作战能力。该项目的最终目标是使用集群规模数量在250个以上的异构集群，在8个城市街区，自主执行超过6小时的区域隔绝任务。OFFSET项目共设置了九项外场试验测试，目前前四项测试已经完成，已签发第五项针对集群战术设计的项目合同，原计划于2020年12月进行实际的外场测试。此外，DARPA还发布了其他多种基于无人机集群的研究项目，包括但不限于：(1) 致力于设计快速部署、廉价可重复使用的集群作战设备的“小精灵”(Gremlins)项目；(2)专注于低成本、大规模部署的集群项目LOCUST；以及(3) 寻求可快速集成新技术而无需大规模重新设计的“体系集成技术和试验”（SoSITE）项目等。

%\begin{figure}[htbp]
%	\centering	
%	
%	\subfigure{\label{subfig. discretizationArea}}\addtocounter{subfigure}{-2}
%	\subfigure[leftfig]{\subfigure[第三阶段任务示意图]{\includegraphics[width = 0.45\textwidth]{figures/offset_concept.jpg}}}	
%	\null\hfill
%	\subfigure{\label{subfig. discretizationBoundary}}\addtocounter{subfigure}{-2}
%	\subfigure[leftfig]{\subfigure[待执行第三阶段试飞任务的虎鲨无人机]{\includegraphics[width = 0.45\textwidth]{figures/OFFSET_content.png}}}
%	
%	\bicaption[fig. PDOPdiscretizationAreaBoundary]{}{OFFSET项目}{Fig.$\!$}{Gradient of the objective on the coverage boundary}
%	\vspace{-0em}
%\end{figure}

\begin{figure}[htbp]
	\centering	
	
	\subfigure{\label{subfig. discretizationArea}}\addtocounter{subfigure}{-2}
	\subfigure[TB2: The UAV used by Azerbaijan from Turkey]{\subfigure[阿塞拜疆使用的土耳其TB2无人机]{\includegraphics[width = 0.45\textwidth]{figures/TB2.png}}}	
	\null\hfill
	\subfigure{\label{subfig. discretizationBoundary}}\addtocounter{subfigure}{-2}
	\subfigure[UAV executes missions in battlefield]{\subfigure[无人机执行目标清除任务]{\includegraphics[width = 0.45\textwidth]{figures/TB2_ATTACK.png}}}
	
	\bicaption[fig. PDOPdiscretizationAreaBoundary]{}{亚阿冲突中的无人机}{Fig.$\!$}{The application of UAV in Nagorno-Karabakh war}
	\vspace{-0em}
\end{figure}

除了处于研究阶段的集群作战概念，未来军事和战争形势无人化、集群化以及自主化的趋势和优势已经在近期的局部冲突中得到了全方位的展现和彰显。2019年9月14日，也门胡塞运动武装出动10架次无人机，同时对沙特阿拉伯国家石油公司（简称沙特阿美）位于沙特阿拉伯布盖格的“世界最大石油加工设施”和位于胡赖斯的一个特大油田进行了饱和式攻击。袭击造成造成的损失直接导致沙特阿拉伯每日原油产量减少570万桶，占全球每日原油供应量的5$\%$。与此相比，位于布盖格的石油设施曾经在2006年遭基地组织使用人肉炸弹试图袭击，但最终被安全部队瓦解。因此，无人机集群仅以极小的代价实现了巨大的战术价值。此外，2020年攻击型无人机被广泛应用于亚美尼亚和阿塞拜疆冲突。虽然在此次冲突中集群协同作战的概念没有体现，但是无人机的高防空拦截难度，低成本、易操作的优势被凸显，战争思维正发生转变。依靠使用察打一体式、混合编组的无人机集群进行战斗，来执行高价值目标歼灭任务，阿塞拜疆牢固掌控了前线制空权，取得了巨大的战略价值。



% 当前研究内容和已有的系统，研究方案等
%机器人集群系统在多个民用领域也拥有广阔的应用前景。在精准农业方面，采用异构的机器人集群可以代替人工进行全自动精准作业，包括精确播种、施肥、农药喷洒、除草、灌溉、收获等工作。2015年，欧盟“2020地平线”计划和瑞士国家教育研究和创新基金共同推出了“萌芽”（Flourish）项目，旨在开发新型机器人协作农业生产体系，自适应地处理不同作物和多种农业任务，减少人的参与，解决当前农业机器人功能单一的问题。该项目采用小型无人机与多用途地面机器人进行协作，可执行空中信息采集、地面作业、为农户提供信息和决策支持等功能。通过选择合适的传感器，该协作系统可以对不同的农作物田地进行各种任务的自主作业。2018年项目结题时，设计的无人机具备每小时巡视0.1$km^2$的农田，生成作物态势感知地图，自主优化飞行路径，以及向地面机器人发送感知数据的能力。依靠无人机的感知信息，地面机器人可执行自主导航，通过图片识别技术分辨农作物种类，测量作物生长高度、肥力状态以及评估植物的健康水平，并且可以有选择性地对特定区域植物进行农药喷洒、施肥以及除草等操作。通过精准施策可以有效地减少由农药和化肥导致的化学污染，并显著地提高农业生产效率，减少人力的介入。
%\begin{figure}[htbp]
%	\centering	
%	
%	\subfigure{\label{subfig. discretizationArea}}\addtocounter{subfigure}{-2}
%	\subfigure[leftfig]{\subfigure[“萌芽”项目总体示意图]{\includegraphics[width = 0.45\textwidth]{figures/flourish_overview_reduced.png}}}	
%	\null\hfill
%	\subfigure{\label{subfig. discretizationBoundary}}\addtocounter{subfigure}{-2}
%	\subfigure[leftfig]{\subfigure[无人机和地面机器人协作示意图]{\includegraphics[width = 0.45\textwidth]{figures/flourish_paper_solution.png}}}
%	
%	\bicaption[fig. PDOPdiscretizationAreaBoundary]{}{智慧农业}{Fig.$\!$}{Gradient of the objective on the coverage boundary}
%	\vspace{-0em}
%\end{figure}
%
%自动驾驶技术的成熟驱动着城市交通体系向车路协同方向的快速发展。车路协同是指利用车载传感器，或设置在道路上的传感装置，在监测和获取车辆与道路实时信息后，通过车车、车路之间的通信交互手段进行数据共享，优化利用交通体系的时空资源，实现车辆之间、以及车路之间的协同配合、协同决策，从而提高交通效率，保障交通安全。欧美日等发达国家早在本世纪初就积极投入车路协同的关键技术研究，包括美国的“IntellIDrive$^{SM}$”项目，欧盟的“eSafety”计划，以及日本的“Smartcar”项目等\citeup{陈超2011国内外车路协同系统发展现状综述}。国内目前也在积极开展车路协同系统的研究和应用工作。2020年6月，作为“交通强国”建设试点城市的雄安，成立了雄安新区绿色智能交通先行示范区，初期建设内容主要包括道路基础设施数字化改造、车辆网联化、车路协同云平台建设等。随着$5G$通讯技术和自动驾驶技术的成熟和应用，全方位智能监控、城市运行态势感知、应急实时响应，边缘计算等需求将得到满足，进一步推进城市智慧化水平。

其次，多智能体系统在服务科学研究、探索未知区域、拓展人类生存空间等方面也扮演者重要角色。使用化学反应、磁场、超声波、光、电等外力驱动的微纳米机器人，在群体智能的“指挥”下，可以穿过复杂的生物结构或者狭窄的毛细血管，进行局部诊断、成像、运载活检样本、靶向释放药物等操作\citeup{li2017micro}。基于视觉和单点光源非直接交互形式的仿生鱼形机器人可以在深海GNSS信号拒止环境、电磁通信受阻、以及复杂的洋流扰动下实现自主协同控制、相对定位和构型保持，通过简单的自组织规则实现鱼群的逡巡、环绕等群体状态\citeup{wolek20213d,berlinger2021implicit}，为未来探索深海环境，实施海底地质探测、探寻生物多样性、研究洋流等海洋现象等任务提供了可行的潜在方法。

\begin{figure}[htbp]
	\centering		
	\subfigure{\label{subfig. discretizationArea}}\addtocounter{subfigure}{-2}
	\subfigure[The Ingenuity flying with the Preservence]{\subfigure[机智号飞行示意图]{\includegraphics[width = 0.45\textwidth]{figures/MARS_Igenuity.jpg}}}	
	\null\hfill
	\subfigure{\label{subfig. discretizationBoundary}}\addtocounter{subfigure}{-2}
	\subfigure[The composition of the Ingenuity]{\subfigure[机智号系统组成]{\includegraphics[width = 0.45\textwidth]{figures/MARS_Helicopter_composition.png}}}
	
	\bicaption[fig. Ingenuity]{}{第一架火星无人直升机“机智”号(图片来源：NASA)}{Fig.$\!$}{The first flying vehicle on the Mars: the Ingenuity helicopter, source NASA}
	\vspace{-0em}
\end{figure}

最后，多智能体系统将极大提升人类太空探索的效率。
%在2018年国际太空探索协调工作组（ISECG）发布的《全球探索路线》报告中，着重强调了机器人技术对未来太空探索任务的支撑作用。
2020年，美国国家航空航天局（NASA）发布的《月球可持续探索和发展规划》报告提到，多月球着陆器可以为人类提供探测月表结构和月球资源的全局分布视野。机器人探测器将会更被为广泛地使用在未来的月球探测任务中，通过携带多样的科学探测设备，用于探索和开采月球珍惜资源，如液态水、氧气、稀土等。2021年2月18日，搭载有火星第一架无人直升机“机智号”的美国“毅力号”火星车成功降落在火星杰泽罗陨石坑。机智号重1.8公斤，高0.5米，螺旋桨直径1.2米，由两个反向旋转的螺旋桨提供升力，功率350瓦。
如表~\ref{tab. IngenuityTests}，截至到2021年5月7日，机智号已经完成了全部5项预设的飞行测试任务，在未来将规划与火星车执行联合探测任务。
%无人直升机计划在探测器着陆火星表面至少一个月后，预计在30天测试期内进行五次飞行。
%首先将开展离火星表面15英尺的短距垂直测试，然后将沿着飞行方向来回进行约150英尺的水平飞行。
可以预见，未来的火星探测方式将从以路基探测为主转变为空地协同探测。空间机器人可以发挥其机动性和视野优势，为地面机器人提供全局感知信息，协助执行负载运送、地形勘探、定位与建图等功能，从而可以大幅提高火星探索效率\citeup{balaram2018mars}。


\begin{table}[htbp]
	\bicaption[tab. IngenuityTests]{}{机智号五项测试任务}{Table$\!$}{Statistics for the ingenuity helicopter flying tests on the Mars}
	\centering \vspace{0.5em}
	\wuhao		
	\begin{tabularx}{\linewidth}{cccccX}
		\toprule[1.5pt]
		编号& \begin{tabular}[c]{@{}c@{}} 时间\\(UTC) \end{tabular} & \begin{tabular}[c]{@{}c@{}} 飞行\\时长(s) \end{tabular} & \begin{tabular}[c]{@{}c@{}} 高度\\峰值(m) \end{tabular}  & \begin{tabular}[c]{@{}c@{}} 飞行\\路程(m) \end{tabular} & 任务概括 \\ 
		\midrule[1pt]
		1    & 2021/04/19  & 39.1        & 3         & 0    & 垂直起飞-悬停-原地降落    \\
		2    & 2021/04/22  & 51.9        & 5         & 4.3  & 垂直起飞-悬停-向西飞行-悬停-返回-悬停-降落  \\
		3    & 2021/04/25  & 80          & 5         & 100  & 垂直起飞-悬停-向北飞行，最大速度2m/s-悬停-返回-悬停-降落  \\
		4    & 2021/04/30  & 117         & 5         & 266  & 垂直起飞-悬停-向南飞行，最大速度3.5m/s-悬停-返回-悬停-降落  \\
		5    & 2021/05/07  & 108         & 10        & 129  & 垂直起飞-悬停-向南飞行，最大速度3.5m/s-上升至10m高度-悬停-降落  \\
		\bottomrule[1.5pt]
	\end{tabularx}
\end{table}

\BiSubsection{构型协同控制方法研究现状}{Current research for configuration control}

编队控制是多智能体系统的热点研究方向之一，它的目的是通过节点之间的通信和协作，使得多智能体系统的所有节点之间在空间上的相对状态符合预设的队形约束。经过几十年的发展，编队控制已经积累了大量的研究成果\citeup{Wang2013Survey,Hu2012Formation,olfati2007consensus,ren2005survey,ren2010distributed,chen2005formation}，可以按照控制律所需的输入数据的类型，划分为如下三类\citeup{oh2015survey}：

(1) 基于绝对位置信息的编队控制方法。网络内的智能体可以感知它们在绝对坐标系下的位置状态。智能体将该绝对位置作为已知信息反馈到构型控制过程中，主动地控制自身状态，使其最终收敛到期望队形。由于期望队形也是通过给定每个节点最终的期望位置的方式来定义的，因此，仅通过位置环的反馈控制就可以实现编队控制效果。此时，网络内部的通信交互对编队控制没有直接影响，多智能体系统可以利用通信数据实现一些额外的队形目标，例如通过一致性实现队形保持或者队形同步等。根据智能体动力学进行划分，基于绝对定位信息的编队控制方法包括对积分器模型\citeup{ren2007distributed,ren2005consensus}、通用线性模型\citeup{fax2002information,fax2002graph,fax2004information}、非完整约束模型\citeup{dong2008cooperative,dong2008formation,dong2009decentralized}的研究。更多基于绝对位置信息的编队控制方法可参见文献\cite{lewis1997high,tan1996virtual,beard2001coordination,young2001control,do2007nonlinear}。

(2) 基于相对位置信息的编队控制方法。与前一种方法有所不同，此处的智能体不需要观测它在绝对坐标系下的位置，只需要观测在自身局部坐标系下它的邻接节点与自己的相对位置。此类方法需要所有节点的局部坐标系之间保持旋转方向上的对齐。此时多智能体系统的期望队形是由所有邻接节点对之间的期望相对位置所定义的，因此节点之间必须通过交互和协作才能控制自身状态来实现期望队形。根据智能体动力学进行划分，基于相对位置信息的编队控制方法包括对一阶积分器模型\citeup{olfati2004consensus,ren2010distributed,ren2005coordination,jadbabaie2003coordination,moreau2005stability,lin2007state}、二阶积分器模型\citeup{ren2007distributed,ren2007information}、通用线性模型\citeup{fax2002graph,fax2004information,zhang2015lqr,li2009consensus,wen2014distributed}、非完整约束模型\citeup{lin2005necessary,dimarogonas2008connection}等。

(3) 基于相对距离测量的编队控制方法。此时，智能体只可以获得它自身与邻接节点之间的相对距离。此类方法中每个智能体的局部坐标系之间不需要保持对齐。期望构型的定义是由一组两两节点之间的相对距离序列所给定的。由于相对距离测量与坐标系的平移和旋转都无关，因此给定的相对距离序列与期望队形之间并不是一一对应的关系。为了避免该问题，目前基于相对距离测量的编队控制方法在给定期望队形的相对距离序列时，需要定义额外的空间拓扑约束。例如对于无向的空间拓扑，由相对距离序列定义的期望队形必须是刚体图\citeup{oh2015survey,anderson2008rigid,oh2014distance,krick2009stabilisation,dasgupta2011controlling,belabbas2012robustness}；对于有向的空间拓扑，期望队形必须是持续图\citeup{summers2011control,anderson2011maintaining,kang2014distance,dorfler2010geometric}。

\begin{figure}[htbp]
	\centering		
	\includegraphics[width = 0.95\textwidth]{figures/ArchConfiguration.eps}	
	
	\bicaption[fig. ArchConfiguration]{}{航空集群构型分层控制结构与事件触发-规则驱动演化机制示意图\citeup{Liang2018Con}}{Fig.$\!$}{Layerouts of the aerial swarm and the event-rule-based evolution framework, source \cite{Liang2018Con}}
	\vspace{-0em}
\end{figure}

除上述三类编队控制方法之外，其他的编队控制方法还有包括基于估计器的方法、基于简单自组织规则的控制方法、基于角度观测的控制方法等\citeup{oh2015survey,li2019survey}。

构型控制的本质是交感拓扑下的编队控制问题。当前学界对构型控制的研究主要是在编队控制和多智能体一致性控制的基础上引入交感拓扑约束，包括通信过程约束\citeup{dehghani2016communication,hsiao2019communication}、相对测量约束\citeup{wang2020circle,yu2020relative}、交互框架设计\citeup{ambroziak2015two,胡利平2016航空集群定位编队协调构型控制研究}等。文献\cite{Liang2018Con}的研究认为，“构型的控制与演化向上必须坚持面向任务的基本原则,向下需要兼容不同动力学特性的异构平台”。图~\ref{fig. ArchConfiguration}是文献\cite{Liang2018Con}针对航空集群提出的构型分层控制结构与事件触发-规则驱动演化机制。由图中可以看出，构型控制处于高层任务和底层动力学平台的中间地带。因此构型控制框架需要从任务层获取高层任务指令，并通过交感网络对环境进行态势评估，然后依据经验根据任务和评估结果对期望构型进行映射，然后在动力学层面经过构型生成、保持、重构、跟踪等指令实现相应的构型变化，从而满足顶层任务需求。

\BiSubsection{构型规划方法的研究现状}{Current research for configuration planning}

路径规划是实现智能体在任务空间内自主运动的关键技术之一，是指智能体通过规划自身的路径序列或者是运动序列，使得智能体可以自主地、安全地、无碰撞地在任务空间中从起始状态运动到目标状态。
当网络内所有节点在规划期限内的路径序列全都确定后，多智能体系统的构型也会随之确定。因此构型规划的本质是在交感拓扑下的多智能体系统路径规划问题。当前研究成果中，对多智能体系统的路径规划方法的研究大多是从单体规划方法拓展而来的。因此本小节首先对单体的路径规划方法进行归纳。如图~\ref{fig. PathPlanArc}所示，这些方法总体上可分为如下四种类型：


(1) 基于图分解的路径规划方法。这些方法的特点是通过离散化，将任务空间分解成网格，用以标识任务空间中的自由区域和存在障碍的区域。由此，将自由空间的网格当作节点，相邻的节点存在连通的边，则任务空间可以建模为包含所有节点和边的一张图。因此，路径规划任务可以在图论知识的帮助下，通过寻找从起始节点到最终节点的连通路径得到。基于图分解的路径规划方法主要包括三类典型算法，分别为Dijkstra算法\citeup{johnson1973note}、 $A^{\star}$算法\citeup{duchovn2014path,lavalle2006planning}以及$D^{\star}$算法\citeup{stentz1997optimal}等。


(2) 基于概率抽样的路径规划方法。与前一种方法有所不同，基于概率抽样的方法不需要将整个任务空间进行离散化，而是通过已知的环境先验信息进行抽样，落在自由空间中的样本点将和与其最近的其他样本点在自由空间中建立连通，并被加入环境特征图。由于样本点的选取存在随机性，因此基于概率抽样的路径规划方法不是完备的，即在某些特殊环境下，即使存在可行解，此类方法也不一定可以找到。基于概率抽样的方法一般可以按照是否返回最优解分类为主动方法和被动方法。其中被动方式主要包括概率路图\citeup{boor1999gaussian,lavalle2006planning}(Probabilistic Road Map, PRM)方法，以及基于泰森分割\citeup{erwig2000graph}(Voronoi Diagrams, VD)的方法。主动方式包括快速搜索随机树\citeup{karaman2011anytime}(Rapidly exploring Random Trees, RRT)方法、人工势场\citeup{park2001obstacle}(Artificial Potential Field, APF)方法等。

\begin{figure}[htbp]
	\centering		
	\includegraphics[width = 0.95\textwidth]{figures/PathPlanArc.jpg}	
	
	\bicaption[fig. PathPlanArc]{}{路径规划方法分类总结\citeup{madridano2021trajectory}}{Fig.$\!$}{Diagram of path planning algorithms, source \cite{madridano2021trajectory}}
	\vspace{-0em}
\end{figure}

(3) 基于数学模型的路径规划方法。此类方法一般聚焦于复杂的智能体动力学和运动学模型，在给定目标(代价)函数后，通过求解优化问题，得出满足动力学约束的优化路径，因此法也被称为轨迹规划问题。按照求解优化问题所使用的优化方法进行分类，此类路径规划问题包括三类典型方法，分别为：混合整数线性规划\citeup{floudas2005mixed}(Mixed Integer Linear Program, MILP)方法、混合整数二次规划\citeup{lazimy1982mixed}(Mixed Integer Quadratic Program, MIQP)方法、以及基于优化控制\citeup{yang2016survey}(Optimal Control, OC)的方法。

\begin{table}[htbp]
	\bicaption[tab. SumPathPlanningMAS]{}{多智能体路径规划方法总结}{Table$\!$}{Research summary of path planning algorithms in multi-agent system}
	\centering \vspace{0.5em}
	\wuhao		
	\begin{tabularx}{\linewidth}{ccXXc}
		\toprule[1.5pt]
		\multicolumn{1}{c}{方法}  & \multicolumn{1}{c}{算法} & \multicolumn{1}{c}{优势}  & \multicolumn{1}{c}{劣势}  & \multicolumn{1}{c}{文献} \\
		\midrule[1pt]
		\multirow{7}{*}{\begin{tabular}[c]{@{}c@{}}图\\ 分\\ 解\\ 方\\ 法\end{tabular}}     
		& Dijkstra    & \begin{tabular}[c]{@{}l@{}}1. 易于实现\\ 2. 离散空间下可获得最优解\end{tabular}                 & \begin{tabular}[c]{@{}l@{}}1. 计算复杂度较高\\ 2. 面向静态环境\end{tabular}                & \cite{mac2017hierarchical,bai2019distributed,chen2019coordinated}  \\
		& $A^{\star}$ & \begin{tabular}[c]{@{}l@{}}1. 离散空间下可获得最优解\\ 2. 导向性快速搜索\\ 3. 在线部署\end{tabular}    & \begin{tabular}[c]{@{}l@{}}1. 大尺度环境下\\ 计算复杂度较高\\ 2. 面向静态环境\end{tabular}       & \cite{erokhin2018optimal,le2018modified,boroujeni2017flexible,sun2019novel}  \\
		& $D^{\star}$ & \begin{tabular}[c]{@{}l@{}}1. 离散空间下可获得最优解\\ 2. 导向性快速搜索\\ 3. 适用于动态环境\end{tabular} & \begin{tabular}[c]{@{}l@{}}导向性依赖于不\\ 真实的距离函数\end{tabular}                     & \cite{peng2015multi}  \\
		\midrule[0.5pt]
		\multirow{8}{*}{\begin{tabular}[c]{@{}c@{}}概\\ 率\\ 抽\\ 样\\ 法\end{tabular}} 
		& PRM         & \begin{tabular}[c]{@{}l@{}}1. 计算过程可以重复使用\\ 2. 大尺度环境快速搜索\end{tabular}             & \begin{tabular}[c]{@{}l@{}}1. 非优化解\\ 2. 被动方式\end{tabular}                     & \cite{madridano2019multi,madridano20203d}  \\
		& VD          & \begin{tabular}[c]{@{}l@{}}1. 易于实现\\ 2. 计算复杂度低\end{tabular}                      & \begin{tabular}[c]{@{}l@{}}1. 被动方式\\ 2. 收敛性没有保障\\ 3. 面向静态环境\end{tabular}      & \cite{chen2017path,kim2020voronoi}  \\
		& RRT         & \begin{tabular}[c]{@{}l@{}}1. 计算复杂度低\\ 2. 快速计算\end{tabular}                      & 只能返回单个可行解                                                                     & \cite{cui2015mutual,solovey2015finding,solana2017multi}  \\
		& APF         & \begin{tabular}[c]{@{}l@{}}1. 时间复杂度低\\ 2. 在线部署\end{tabular}                      & 局部最优                                                                          & \cite{hassan2017global,ying2015leader}  \\
		\midrule[0.5pt]
		\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}}数学\\ 模型\\ 方法\end{tabular}} 
		& MILP        & 可获得完备的系统和环境信息                                                                    & 时间复杂度较高                                                                       & \cite{song2016rolling}  \\
		& MIQP        & 比MILP求解速度更快                                                                      & 数学模型复杂                                                                        & \cite{kushleyev2013towards,mellinger2012trajectory}  \\
		& OC          & 考虑控制过程                                                                           & 非解析解                                                                          & \cite{spurny2019cooperative,luis2020online} \\
		\midrule[0.5pt]	
		\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}}生物\\ 启发 \\ 方法\end{tabular}}         
		& NN          & 不要求环境先验信息已知                                                                      & \begin{tabular}[c]{@{}l@{}}1. 解的形式不直观\\ 2. 求解过程的成功与否与\\ 网络参数和训练过程相关\end{tabular} & \cite{cruz2017path} \\
		& EA          & 可以解NP-hard和多目标问题                                                              & 时间复杂度较高                                                                       & \cite{zhen2020rotary,nazarahari2019multi} \\
		\bottomrule[1.5pt]
	\end{tabularx}
\end{table}

(4) 基于生物启发式的路径规划方法。此类方法试图通过模拟生物的表现与行为来求解路径规问题。此类方法主要有三个典型特点\citeup{pena2016inverse}，首先是它们不需要详尽地了解任务环境的全部特征，其次这些方法一般都可以通过并行处理减少问题复杂度，最后它们可以自适应地处理复杂目标或多目标问题。典型的生物启发式路径规划方法有基于学习的神经网络\citeup{glasius1995neural}(Neuronal Network, NN)方法，以及进化算法\citeup{back1996evolutionary}(Evolutionary Algorithms, EA)等。

最后，近十年来，有大量的研究成果已经将上述对单体系统的路径规划方法拓展到多智能体系统的任务中。表~\ref{tab. SumPathPlanningMAS}总结了近年来针对多智能体路径规划问题最新研究进展。

\BiSubsection{协同定位方法的研究现状}{Current research for cooperative localization}

精准的自定位功能是多智能体系统实现众多协同自主任务的基础技术之一\citeup{李德仁1997论,tetley2007electronic,mautz2009challenges,paull2013auv}。在日常生活中，GNSS可以为大部分的应用提供精准且易获取的定位导航信号。全球导航卫星系统（GNSS）是指在近地空间固定轨道上为地面用户提供全天候定位、导航与授时功能的天基无线电导航定位系统。授时定位精度高、覆盖区域广、全天候全天时服务是该系统的显著优势。当前GNSS提供的民用导航精度一般为10m。如果辅助以新型定位手段和解算方法，如精密单点定位技术\citeup{刘经南2002gps}（PPP）和网络实时差分方法(Network RTK)等，定位精度可提升至厘米、甚至毫米级别\citeup{宁津生2013全球导航卫星系统发展综述}。因此，一般的任务环境下，GNSS可以为大部分的应用提供精准、可靠、易获取的定位导航需求。然而GNSS信号仍然存在诸多弱点和缺陷。在一些特殊任务中，GNSS无法提供可靠的定位表现。GNSS受限拒止的环境大致可归纳为如下三类情况：

(1) GNSS导航信号传输距离远，受空间衰减、电离层干扰以及多径效应的影响，定位信号到达地表用户时能量低、穿透性差、单向特性不明显。因此在市区、室内、深海等环境中，GNSS信号无法提供高精度服务。

(2) 同样由于信号强度较低，在对抗环境中，GNSS信号易受到电磁干扰、屏蔽等威胁。另外导航电文格式是公开信息，基于GNSS定位的系统容易受到假信号的欺骗和诱导。因此在对抗环境下，GNSS是不可靠的。

(3) GNSS服务的有效范围仅局限于地球表面，因此外太空探索任务，如月球基地建设，火星表面巡视等，无法依赖于GNSS定位方案。


因此在GNSS拒止的环境中，移动平台只能通过搭载各类传感器，对环境和自身的运动信息进行感知，然后通过融合自身各类传感器的感知数据，实现自定位的功能。不过由于运动过程中受到的外部扰动和传感器观测过程中存在的随机噪声的影响，节点通常无法获得精确的定位信息。

多智能体系统的协同定位方法是通过在每个节点上搭载相对观测传感器和通信设备，从而在任务中通过协作的方式（如通过执行相对观测和数据共享），额外地增加定位信息来源，从而优化定位精度的方法。由于协同定位框架中的观测数据是通过协作的方式产生的，而不是依赖于对环境的感知，因此协同定位方法在高对抗、大尺度、具备单一特征、或动态特征的环境中具有优势。

早期对协同定位方法的研究主要集中在估计方法的设计、理论分析\citeup{rantakokko2011accurate,patwari2005locating}以及实验验证\citeup{kurazume2000experimental}等方面。此阶段的研究成果主要包括中心化估计方法，以卡尔曼滤波(Kalman Filter,KF)、扩展卡尔曼滤波(Extended KF, EKF)方法为主\citeup{roumeliotis2003analysis,mourikis2006performance}；以及分布式估计方法，包括KF方法\citeup{roumeliotis2002distributed,olfati2007distributed,wanasinghe2014decentralized}、粒子滤波\citeup{fan2018maximum}、最大后验概率估计\citeup{nerurkar2009distributed}、一致性滤波\citeup{yang2007distributed}、贝叶斯滤波\citeup{leung2009decentralized}等方法。其中文献\cite{mourikis2006performance}使用中心化的EKF估计器，通过理论推导，定性地分析了协同定位方法的稳定性，主要得出如下两个结论：
\begin{enumerate}
	\item[(1)] 当网络中至少有一个节点可以获得绝对状态观测(锚节点，GNSS等)时，多智能体系统的协同定位过程是可观测的(observable)，即协同定位精度的稳态误差上界是常值。反之，如果协同定位过程是不可观测的，则协同定位精度的稳态误差界随时间的增长而发散。
	\item[(2)] 当网络在某一时刻可以重复地执行测量时，协同定位精度受传感器测量精度以及网络内部观测构型的影响，与节点状态的初始不确定性无关，
\end{enumerate}

近年来在无线信号网络(Wireless Sensor Network, WSN)领域兴起的网络定位导航(Network Localization and Navigation,NLN)概念，将协同定位过程等价为导航信息在时空网络中传递过程，因此可以使用信息论等理论工具，使用费舍尔信息矩阵(Fisher Information Matrix, FIM)来衡量时空导航网络中导航信息的数量及其传递过程\citeup{win2018theoretical,shen2010fundamentalA,shen2010fundamentalB,win2011network,mazuelas2011information,mazuelas2018spatiotemporal,mazuelas2012spatio}。文献\cite{shen2010fundamentalA,shen2010fundamentalB}中通过定义等效费舍尔信息矩阵(Equivilent FIM, EFIM)以及Schur补的矩阵操作\citeup{cottle1974manifestations}得出了表征协同定位理论估计精度下界的指标：平方位置误差界(Square Position Error Bound, SPEB)。 通过对SPEB和EFIM的分析，导航信息的传播依赖于相对观测连接，单个节点上导航信息的积累可以分解成局部观测拓扑中每一个观测连接上导航信息流入和流出的累加\citeup{shen2012network}。

因此，无论从估计方法的理论分析，或者是从导航信息传递角度，多智能体系统协同定位过程受到系统配置以及网络实时构型的影响。
%因此如何增加定位信息来源，减少定位过程中的不确定性因素，增加定位精度，成为了多智能体系统在GNSS拒止环境中自定位任务的。
由于多智能体系统都是由合作节点组成的，则针对特定问题设计优化的协同策略可以大幅度提升协同定位的性能。例如文献\cite{hidaka2005optimal}以EKF估计器稳态协方差的迹作为优化指标，使用遗传优化算法对多智能体系统的静态构型进行优化；文献\cite{trawny2004optimized,zhou2008optimal,zhou2011multirobot}分别针对不同任务背景下的协同定位过程设计了优化的运动策略。文献\cite{mourikis2006optimal}针对观测和通信能力受限的问题，对系统内不同节点之间观测连通的观测通信频率进行了优化分配。在NLN研究工作中，文献\cite{win2018network,dai2014distributed}对协同定位网络的四种系统配置进行了优化，分别为节点优先顺序、节点激活序列、系统构型以及能量分配。


%优化的协同策略包括如何更加合理地利用协同测量数据，如何获得最佳的相对观测构型配置以及如何处理信息之间的耦合等方面。主动协同定位方法是指在定位过程中主动地去预测系统在未来时刻的性能表现，从而选择最佳的系统配置，以优化多智能体系统内部对定位过程可能产生影响的各类因素，使相对测量过程更为合理，测量数据更加可靠，定位精度更高。

\BiSubsection{不确定性规划方法的研究现状}{Current research for planning under uncertainty}

主动规划问题是指在当前时刻，依据所获得的历史数据，对未来规划期限内可以改变系统状态的自变量(控制输入)进行序列决策，从而使给定的目标(代价)函数达到最优取值。当系统状态是确定的，且系统状态转移过程是有限的，则此类主动规划问题可以等价为一类马尔可夫决策过程\citeup{puterman2014markov}(Markov Decision Process, MDP), 从而直接调用动态编程\citeup{denardo2012dynamic}(Dynamic Programming, DP)的方法进行有效求解。

然而，由于实际任务中智能体的运动过程和观测过程都存在噪声干扰，系统的状态无法准确观测，只能通过估计的方法得到真实状态的分布情况，即部分可观测。此时，主动规划问题变成了一类典型的部分可观测马尔可夫决策过程\citeup{kaelbling1998planning}(Partially Observable MDP, POMDP)。大量研究结果表明\citeup{monahan1982state,范长杰2008基于马尔可夫决策理论的规划问题的研究,papadimitriou1987complexity}，虽然系统的状态是有限维度的，但是由于存在状态不确定性，POMDP问题的解需要在一个包含所有可能状态分布的无穷维度空间中进行搜索，会产生“维度灾难”现象(Curse of dimensionality)。因此POMDP问题具有极高的问题复杂度，目前学界尚不存在对通用POMDP问题求最优解的可行方法。仅有少数低维度、小规模的POMDP问题可以被成功求解\citeup{kaelbling1998planning,ross2008online}。

信念空间规划(Belief Space Planning, BSP)是一类典型的POMDP问题，它通过调用估计方法对未来规划期限内系统状态进行预测，将所有可能的状态预测分布定义为信念空间(Belief Space)，然后在这个连续的信念空间中搜索POMDP问题的解。由于POMDP问题的超高复杂度，目前针对BSP问题的研究主要集中于牺牲解的最优性，即放弃寻找全局最优解，以降低问题的计算复杂度。根据对信念空间处理方式的不同，最新的BSP求解方法可以大致分为两类，分别为离散化空间方法以及连续空间方法。离散化方法将状态的信念空间、运动空间以及测量空间按照一定规则进行离散化，使用离散后有限维度的集合代替原本无穷维度的状态、运动空间，具体的离散化过程包括概率抽样方法\citeup{agha2014firm,pathak2018unified,prentice2009belief,alterovitz2008constant,alterovitz2007stochastic}，仿真离散方法\citeup{stachniss2005information},点价值迭代方法\citeup{pineau2006anytime,porta2006point,ong2010planning,kurniawati2008sarsop}等。连续的信念空间的规划方法一般也被称作直接轨迹优化方法，需要在给定的一组初始路径上，通过DP方法，梯度下降方法\citeup{indelman2015planning,platt2010belief,patil2015scaling}或者LQG\citeup{van2012motion}等方法对标称轨迹进行更新迭代。

另外，除上述总结的方法外，在降低计算复杂度的方向上，文献\cite{kopitkov2017no}和\cite{kopitkov2019general}分别就目标函数评估过程和未来状态的后验协方差计算过程的计算复杂度进行了研究，通过对比临近控制输入之间目标函数计算过程的相似性以及使用稀疏矩阵特性减少了POMDP问题的计算复杂度；文献\cite{farhi2019ix}采用递增的协方差预测方法减少了POMDP在预测过程的计算复杂度。最后，一些启发式的求解方法，如基于蒙特卡洛树搜索的方法\citeup{silver2010monte}或者基于确定性部分可观测稀疏树搜索的方法\citeup{somani2013despot}，不需要在求解的过程中进行信念更新，因此它们可以用来求解一些大规模POMDP问题，但是这些方法缺乏理论保障。

当前对不确定性规划的研究对象依然大多针对单个机器人或智能体，对多智能体系统的研究仍存在较大的困难。主要是由于维度爆炸现象的限制，由于单体POMDP问题已经具有超高的问题复杂度，当已有的针对单体POMDP问题的解决方法应用到多智能体系统的任务时，问题的状态维度将随着多智能体系统的规模而成倍增加，最终导致问题复杂度以指数规模增加。文献\cite{regev2018decentralized,regev2016multi}研究了未知环境中多个机器人信念空间规划的问题，提出了一类分布式决策框架，使每个节点根据局部信息进行独立决策，然后通过交互网络向邻接节点广播自己的决策、接收邻接节点的决策信息，最后通过迭代实现分布式的路径规划。虽然该方法通过利用多个控制输入的相似性，重复利用相似控制输入下目标函数评估中的计算过程，从而在一定程度上降低了运算复杂度，但是该方法的计算复杂度仍将随着规划周期的增加而指数增长；且该过程采用离散化空间方法生成候选控制输入，因此需要已知目标构型。

\BiSubsection{存在的问题和挑战}{Existing challenges and problems}

当前多智能体系统构型控制和规划研究领域的研究方法在处理拒止环境任务时仍然存在以下几点问题：

(1) \textbf{基于相对观测的构型控制问题.}

空间拓扑下的传统编队(队形)控制问题通常假定智能体在绝对坐标系下的状态是已知的，通过定义每个节点的期望状态来给定系统的期望构型。此时，可以通过单独控制每一个独立节点的位置来实现期望构型。系统内部节点之间的感应与交互行为的主要目的是为了增强控制性能或者实现队形保持。然而拒止环境中节点绝对状态是不可观的，或对它的观测是不可靠的，因此必需进一步研究基于节点内部相对观测数据的特定构型协同控制问题。

(2) \textbf{构型控制与定位过程存在耦合的问题.}

虽然相对测量可以用于解决构型控制问题，但是获取节点的位置状态，即对节点进行定位，依然是多智能体系统在拒止环境中执行许多实际任务的基础。由于拒止环境存在高度不确定性，多智能体系统只能通过交感网络内较为可靠的相对观测来估计节点状态。已有的研究表明，在基于相对观测的协同定位过程中，网络内部的相对观测构型是定位精准度的重要影响因素之一。然而当前对协同定位的研究大多关注状态估计方法的研究，或者仅是对构型与定位的耦合关系进行定性分析。然而针对使用构型变换和构型控制减少定位误差的相关研究成果较少，且大多缺乏实际指导意义。


(3) \textbf{构型规划中状态存在不确定性的问题.}

环境中的不确定性主要来自两方面，其一是由于智能体运动过程存在未建模的运动学、动力学模型，或存在外部扰动；其二是智能体观测过程存在噪声。因此无论使用哪一种基于数据融合的状态估计方法都无法获得节点的真实状态，只能获取对节点状态分布(即信念状态)的估计。在信念空间中对多智能体系统的构型规划问题是一类典型的部分可观测马尔可夫决策过程。由于信念空间实际上是一类由有限维度状态所组成的具有无限维度的空间，因此POMDP问题存在“维度灾难”和“历史灾难”的限制，目前只有小规模和低维度的POMDP问题的最优解可以被计算。多智能体系统是由多个节点组成的复杂网络，面向构型规划的POMDP问题需要考虑每一个节点的状态，因此将面临更为严峻的“维度灾难”问题。

(4) \textbf{未来观测拓扑是时变随机的.}

此外，当系统内的交互、观测传感器由于受到实际因素的限制时，多智能体系统内部的交感拓扑是时变的，此时，状态不确定性也必导致多智能体系统无法准确预测未来的交感拓扑结构。


\begin{figure}[htbp]
	\centering		
	\includegraphics[width = 0.95\textwidth]{figures/relationship.jpg}	
	\bicaption[fig. Relationships]{}{研究内容与各部分之间的关系}{Fig.$\!$}{The research contents and relationships}
	\vspace{-0em}
\end{figure}

\BiSection{主要研究内容与章节安排}{Outline of the thesis}

本学位论文的整体思路以及各部分之间的关系如图~\ref{fig. Relationships}所示。其中主要研究内容与文章组织架构之间的关系如图~\ref{fig. PaperStructure}所示。第二章和第三章研究两种特殊构型的控制方法，即基于相对测量的包围构型以及面向定位任务的PDOP构型，分别对应中的问题(1)和问题(2)。第四章和第五章是两种构型规划方法，旨在通过构型规划提升协同协同定位过程在受到环境不确定性影响时的鲁棒性。因此第四章的研究内容对应问题(2)和(3)，即考虑系统状态存在不确定性构型规划问题；第五章以第四章的研究内容为基础，研究时变的交感拓扑对信念空间构型规划方法的影响，即问题(4)。 


% 。其中第二章对应于第一点研究内容，第三章对应于第二点研究内容，第四章和第五章对应于第三点研究内容。各个章节之间的关系是层级递进的。第二章的研究目的是形成一类给定的构型，不许考虑其他约束，因此当GNSS受限拒止时，该控制方法不需要对节点位置进行估计，仅采用相对观测数据就可以实现特定包围队形控制；不过第三章和第四、五章的研究内容不再是对某类给定构型的控制，而是探索构型变换对终端任务的影响，其中第三章考虑部分节点GNSS拒止，利用一部分位姿状态已知的节点为未知节点提供定位导航服务，并研究集群构型对移动定位系统定位导航服务精度的影响；第四、五章研究全域GNSS拒止环境下集群构型对协同定位过程的影响，通过规划集群路径，优化未来时刻的集群内部的相对观测。

本学位论文的主要研究内容概括如下：


%1) 二阶集群系统基于事件驱动的快速一致性协同控制方法：

%一致性是集群系统协同控制问题的基础，在复杂环境中，尤其是对抗环境中，协同控制过程往往需要满足多方面的性能要求。本文重点研究在两种特殊性能指标耦合约束下，协同一致性控制率的设计问题。第一个指标是减少控制器的更新频率，集群中的个体通常是由一定的机械结构组成的，当控制器通过数学运算输出指令后，执行器根据控制器指令驱动相应机械结构运动，从而实现对个体状态的控制。然而在实际任务中，执行器可能由于存在较大的时间常数，或者在任务执行过程中受到磨损或毁坏，导致其无法及时跟踪控制器的输出频率。此时需要减少控制器的更新频率从而减轻制动器负担。第二个指标是实现一致性的快速收敛，快速收敛特性可以保证集群系统对特定任务做出及时响应。

%因此，论文将事件驱动控制方法与有限时间稳定一致性理论相结合，通过设计特殊的事件触发机制，将一类具有连续输出的有限时间一致性稳定控制器转变为一类跟随事件触发的离散控制器。在该分布式控制率作用下，二阶集群系统不但保持了有限时间稳定的优点，又通过事件触发机制减少了控制器的输出频率。论文论文通过严格的理论推导验证了控制率的稳定性能，并在理论上排除了Zeno现象的发生。

\begin{figure}[htbp]
	\centering
	\includegraphics[width = 0.95\textwidth]{figures/PaperStructure.jpg}
	\bicaption[fig. PaperStructure]{}{论文架构}{Fig.$\!$}{The structure of this thesis}\vspace{0em}
\end{figure}

\textbf{(1)基于相对测量的包围构型一致性协同控制方法：}
%。在对抗环境下，对非合作单位形成包围构型可以用于对其实施监视、打击等后续任务，对合作目标的包围可以实现对重要单位的隐藏和保护功能。在非对抗环境下，包围构型便于集群系统对特定区域的巡视、侦察、信息收集、态势评估等任务。
包围构型在对抗和非对抗的多智能体任务中都发挥着重要的作用。本章主要研究在导航拒止环境下多智能体系统包围构型的协同控制问题。针对具有二阶运动学模型的多智能体系统，考虑GNSS导航信号拒止环境中不使用绝对状态观测，设计基于局部坐标系相对测量的智能体节点加速度分布式一致性协同控制方法。

%本章基于协同一致性和图论等理论，首先假设绝对状态可以获得的情况下，研究一类针对二阶运动学多智能体系统的包围构型分布式控制律。以此为基础，论文进一步考虑在多智能体系统节点无法获取绝对状态观测时，仅使用网络内部相对测量和节点对包围目标的相对测量数据，提出多智能体系统包围构型的分布式协同控制方法。

\textbf{(2)面向PDOP定位构型的构型控制方法：}
本部分主要研究构型控制与协同定位过程的耦合关系，旨在通过构型控制优化提升协同定位的性能。针对移动定位系统，以目标区域的PDOP分布作为构型指标，研究分布式构型控制方法，利用移动节点的机动性拓展定位服务范围，实现移动定位系统对目标区域定位服务的自动覆盖，随目标热点区域切换，以及对自适应系统规模和节点损失等特点。本章将通过严格的理论推导给出覆盖指标对每一个多智能体节点位置状态的偏导数解析表达式，并以此为基础提出基于梯度下降更新的分布式构型控制方法。

%提出针对移动定位导航系统的PDOP定位构型协同该控制方法。首选将PDOP构型的协同控制问题转化为PDOP指标在拒止区域的覆盖控制问题，然后根据WSN领域中的覆盖控制框架，通过严格的理论推导。

\textbf{(3)基于连续信念空间的构型规划方法：}
本章主要研究环境中存在的各种高不确定性，从而导致多智能体系统节点的状态无法完全观测时的构型规划问题。以模型预测控制的求解框架为基础，建立高斯参数化信念空间的构型规划求解过程，设计基于数值梯度的连续信念空间路径生成方法，避免传统的离散化路径生成方法指数增长的计算复杂度问题

%本部分提出了面向状态不确定性的信念空间构型规划方法。首先将存在状态不确定性的构型规划问题转变为信念空间下的路径规划问题，采用最大似然观测假设预测未来时刻系统的内部和外部观测数据，使用基于数值梯度的连续空间路径搜索方法更新待评估路径。该方法无需为多智能体系统赋予期望构型，基于梯度更新的连续空间路径搜索方法只具有多项式复杂度，有效降低了传统离散化规划方法的指数复杂度。




\textbf{(4)基于概率拓扑的构型规划方法：}
本章主要研究观测传感器存在测量边界，且节点状态存在不确定性的构型规划问题。本部分以信念空间构型规划方法为基础，研究一类相对距离观测模型在未来时刻观测拓扑概率精确预测方法，基于合理假设，将距离观测模型的连通随机变量的概率分布建模为一类正态二次型分布。根据正态二次型分布的序列展开定理\citeup{provost1992quadratic}，通过有限项累加近似计算该正态二次型的分布概率，并通过严格的理论推导给出有限项近似截断误差稳定的充分条件。最后将该方法应用到构型规划过程中，提出基于概率拓扑的构型规划方法，提升构型规划对环境不确定性和时变观测拓扑等随机事件的鲁棒性。



%进一步采用有限项近似方法使得该概率分布变为数值可解问题；并提出了一类多项式累加数目自适应确定方法，使得数值计算得出得概率与理论概率得误差小于给定误差值。


%针对构型与定位过程存在耦合的问题，将多智能体系统的构型作为自变量，通过控制系统构型，增强一类移动定位服务方法的性能。
%%为GNSS受限拒止环境中的用户提供可靠的定位导航服务是重要研究课题之一。已有研究成果主要采用伪基站对GNSS信号进行增强、中继和补充。然而在实际的应用案例中，为了确保定位源的精准矫正，地基定位导航服务系统或增强系统的伪基站总是保持静止状态；空基伪基站和天基伪基站总是按照预定义的周期性轨迹进行运动。因此这些解决方案的服务覆盖范围受到伪基站数量的限制，对用户提供的导航服务质量也无法根据需求进行实时调整。本文提出一类使用机器人集群系统搭载伪基站，为GNSS受限拒止区域提供移动的定位导航服务。本文设计了一种基于协同覆盖控制框架的机动策略，使得机器人集群具备主动覆盖目标用户的能力，并在提供定位导航服务的过程中自动地优化内部构型，在线提升定位导航的服务精度。
%
%\textbf{3)：基于概率拓扑规划的协同定位构型优化方法。}
%协同定位方法是GNSS全拒止环境下机器人集群实现定位功能的潜在替代方案之一。集群内部的相对观测构型是影响协同定位精度的重要因素，因此在任务执行过程中，需要对集群进行路径规划以优化未来时刻的相对观测构型，从而保证集群的定位精度需求。现实情况下，由于运动过程存在扰动，以及传感器存在观测噪声，集群个体的定位一般都存在定位误差。因此集群的路径规划无法在状态空间进行，而是需要在信念空间（包含位姿状态和位姿不确定性）进行。在进行路径规划的时刻，规划过程需要根据当前时刻已知信息和给定的控制输入，预测在未来规划期限内集群在信念空间下的表现，从而对给定的控制输入进行评价。由于传感器存在观测约束，集群内部的相对测量拓扑无法实现全连接或保持固定不变，而是随着集群节点之间相对位置的变化而改变的。因此准确预测未来时刻集群内部的相对观测拓扑将提升对给定控制输入的评估精准度，从而提升路径规划性能。已有研究成果中对机器人集群在未来时刻相对观测拓扑概率的预测主要有两种方式：1）：采用最大似然假设，即任意两个节点在未来时刻相对观测存在与否仅与节点位姿状态预测均值和观测模型相关。2）：采用经验近似方法，例如两个节点的未来观测存在与否与节点位姿状态预测均值、位姿状态预测不确定性以及观测模型相关，但是观测连通存在概率的获取仅依采用经验近似方法，如线性模型、随机方式。
%
%本文首先研究一类相对距离观测模型在未来时刻观测拓扑概率精确预测方法，基于合理假设，将距离观测模型的连通随机变量建模为正态二次型分布。本文设计了一类基于M\&P定理多项式序列展开的方法用于计算正态二次型分布；进一步采用有限项近似方法使得该概率分布变为数值可解问题；并提出了一类多项式累加数目自适应确定方法，使得数值计算得出得概率与理论概率得误差小于给定误差值。以此为基础，本文随后将该拓扑概率精准预测方法应用于协同定位构型规划过程，针对协同定位过程中常见的两类数据融合引擎，即滤波引擎和平滑引擎，分别设计了基于精确拓扑概率的目标函数评估方法。

